package problem124_Binary_Tree_Maximum_Path_Sum;

import problem108_Convert_Sorted_Array_to_Binary_Search_Tree.TreeNode;

public class Solution {
	public int maxPathSum(TreeNode root) {
        int[] max=new int[]{Integer.MIN_VALUE};
        dfs(root,max);
        return max[0];
    }
	
	/**
	 * 计算以root节点开始向下的一条sum最大路径的值。
	 * @param root
	 * @param max
	 * @return
	 */
	private int dfs(TreeNode root,int[] max){
		if(root==null)	return 0;
		int left=dfs(root.left,max),right=dfs(root.right,max);
		int currentMax=root.val+Math.max(0, left)+Math.max(0, right);
		max[0]=Math.max(max[0], currentMax);
		return Math.max(root.val, Math.max(root.val+left, root.val+right));
	}
	
	public static void main(String[] args){
		
	}
}
